#include "showplatform.h"
#include "ui_showplatform.h"
#include"myscene.h"
#include<QKeyEvent>
#include<QGraphicsEllipseItem>
#include<QDebug>
#include<QGraphicsView>
#include<QLabel>
#include<QGraphicsItem>
#include <sstream>
#include <iterator>
#include<QTimer>
#include<QGraphicsSimpleTextItem>
#include<QtWidgets>
#include<QScrollBar>

#include <bits/stl_pair.h>
#include "queue"

showPlatform::showPlatform(QWidget *parent) :
    QMainWindow(parent),
    ui(new Ui::showPlatform)
{
    timer=new QTimer;
    ui->setupUi(this);
    scene_init();
    view_init();
    connect_init();
    styleInit();

}

showPlatform::~showPlatform()
{
    delete ui;
}
//场景初始化
void showPlatform::scene_init()
{
    scene=new MyScene();
    QRectF rectTmp = scene->sceneRect();	//获得当前view scene的区域
    QPointF ptTopLeft = rectTmp.topLeft();	//获得区域左上点和右下点坐标
    QPointF ptBottomRight = rectTmp.bottomRight();
    QPointF ptW_H = 5 * QPointF(rect().width(), rect().height());	//这一步主要是为了后边放大区域的范围，0.5这个系数可以修改
    ptTopLeft -= ptW_H;	//左上点向左上方平移
    ptBottomRight += ptW_H;	//右下点向右下平移
    rectTmp.setTopLeft(ptTopLeft);	//按照左上左下点修改rect的大小
    rectTmp.setBottomRight(ptBottomRight);
    scene->setSceneRect(rectTmp);//更新scene rect的范围
}
//视图初始化
void showPlatform::view_init()
{
    ui->gView->setDragMode(QGraphicsView::DragMode::ScrollHandDrag);
    ui->gView->setVerticalScrollBarPolicy(Qt::ScrollBarAlwaysOff);
    ui->gView->setHorizontalScrollBarPolicy(Qt::ScrollBarAlwaysOff);
    //scene->isShowGrid=0;
    ui->gView->setScene(scene);
    ui->gView->setCursor(Qt::CrossCursor);
    //鼠标跟踪
    ui->gView->setMouseTracking(true);
    //区域选择
    //ui->gView->setDragMode(QGraphicsView::RubberBandDrag);
    //抗锯齿
    ui->gView->setRenderHint(QPainter::Antialiasing);
}
//信号连接初始化
void showPlatform::connect_init()
{

    connect(ui->gView,SIGNAL(mousePress(QMouseEvent *)),this,SLOT(on_mousePress(QMouseEvent *)));
    connect(timer,&QTimer::timeout,this,&showPlatform::showPath);
    connect(ui->gView,SIGNAL(mouseMove(QMouseEvent *)),this,SLOT(on_mouseMove(QMouseEvent *)));
    connect(ui->gView,SIGNAL(mouseRelease(QMouseEvent *)),this,SLOT(on_mouseRelease(QMouseEvent *)));
}

void showPlatform::styleInit()
{
    ui->splitter_left->setStretchFactor(1,5);
}





void showPlatform::ShowMessgae(QString s)
{
    QFont font;
    font.setPointSize(10);//字体大小
    font.setFamily("微软雅黑");
    ui->textBrowser->setFont(font);
    ui->textBrowser->insertPlainText(s)  ;
}





void showPlatform::on_mousePress(QMouseEvent *e)
{

    QPoint p=e->pos();
    QPointF pointS=ui->gView->mapToScene(p);
    curID=-1;
    for(int i=0;i<nodes.size();i++)
    {
        int dx = pointS.x() - nodes[i]->pos.x();
        int dy = pointS.y() - nodes[i]->pos.y();
        int dist = sqrt(dx*dx+dy*dy);
        if(dist < size/2)
        {
            curID = i;
        }
    }
    if(curID!=-1)
    {
        if(e->button()==Qt::LeftButton)
        {
            isDragging=1;
            //ShowMessgae(QString::asprintf("当前选中：节点%d,scene坐标：%1.f,%1.f",curID,nodes[curID]->POS().x(),nodes[curID]->POS().y()));

        }

    }
    else
    {
        return ;
    }

}

void showPlatform::on_mouseRelease(QMouseEvent *e)
{
    isDragging=0;
}
void showPlatform::on_mouseMove(QMouseEvent *e)
{


    QPoint p=e->pos();
    QPointF pointS=ui->gView->mapToScene(p);
    if(curID!=-1)
    {

        if(isDragging)
        {
            qDebug()<<"拖拽";
            nodes[curID]->pos=pointS;
            nodes[curID]->setPos(QPointF(pointS.x()-size/2,pointS.y()-size/2));
            nodes[curID]->name->setPos(QPointF(pointS.x()-size/2-18,pointS.y()-size/2-18));
            qDebug()<<nodes[curID]->POS();

            for(int j=0;j<edges.size();j++)
            {

                qreal x1=edges[j]->start->pos.x();
                qreal y1=edges[j]->start->pos.y();
                qreal x2=edges[j]->end->pos.x();
                qreal y2=edges[j]->end->pos.y();
                QPointF cc((x1+x2)/2,(y1+y2)/2);
                QLineF newLine(edges[j]->start->pos,edges[j]->end->pos);
                edges[j]->setLine(newLine);
                edges[j]->weight->setPos(cc);
                scene->update();
            }

        }
    }

}



void showPlatform::on_open_but_clicked()
{
    QString filePath= QFileDialog::getOpenFileName(this,"打开",QCoreApplication::applicationFilePath(),"*.json");
    if(filePath.isEmpty())
    {
        return ;
    }
    else
    {

        //增加清空当前图
        nodes.clear();
        edges.clear();
        scene->clear();
        QFileInfo fileInfo = QFileInfo(filePath);

        QString fileName = fileInfo.baseName();
        qDebug()<<fileName;



        QFile file(filePath);
        file.open(QIODevice::ReadOnly);
        QTextStream in(&file);

        QByteArray allData = file.readAll();
        file.close();
        QJsonParseError json_error;
        QJsonDocument jsonDoc(QJsonDocument::fromJson(allData, &json_error));


        QJsonArray a = jsonDoc.array();
        QJsonArray nodes=a[0].toArray();
        QJsonArray edges=a[1].toArray();
        for(int i=0;i<nodes.size();i++)
        {
            QJsonArray pos=nodes[i].toArray();
            qreal x=pos[0].toInt();
            qreal y=pos[1].toInt();
            QString name=pos[2].toString();
            Node *node=new Node(QPointF(x,y));
            node->name->setPlainText(name);
            this->scene->addItem(node->name);
            this->nodes.append(node);
            this->scene->addItem(node);
        }
        for(int j=0;j<edges.size();j++)
        {
            QJsonArray pos=edges[j].toArray();
            qreal s=pos[0].toInt();
            qreal e=pos[1].toInt();

            Edge *edge=new Edge(this->nodes[s],this->nodes[e]);
            edge->s=s;
            edge->e=e;
            edge->next=this->nodes[s]->edge;
            this->nodes[s]->edge=edge;
            edge->setLine(QLineF(this->nodes[s]->POS(),this->nodes[e]->POS()));
            this->scene->addItem(edge);

            QString weight =pos[2].toString();

            edge->weight->setPlainText(weight);


            this->scene->addItem(edge->weight);
            this->edges.append(edge);
        }


    }
}

void showPlatform::on_set_s_but_clicked()
{
    if(curID==-1)
    {
        QMessageBox::warning(this,"警告","请选择一个节点作为起点！");
        return;
    }

    path.clear();

    start=curID;
    nodes[start]->setBrush(QColor("#0984e3"));
    QString mes=QString::asprintf("设置起点：%d\n",curID);
    ShowMessgae(mes);
}

void showPlatform::on_set_e_but_clicked()
{
    if(curID==-1)
    {
        QMessageBox::warning(this,"警告","请选择一个节点作为终点！");
        return ;
    }
    end=curID;
    nodes[end]->setBrush(QColor("#ff7675"));
    QString mes=QString::asprintf("设置终点：%d\n",curID);
    ShowMessgae(mes);
}

void showPlatform::on_play_but_clicked()
{
    qDebug()<<"当前算法："<<algorithm_name;
    if(algorithm_name=="Dijkstra优先队列") DJPro();
    else if(algorithm_name=="Dijkstra") DJ();
    else if(algorithm_name=="Bellman_ford") bellman_ford();
    else if(algorithm_name=="SPFA") spfa();
    else if(algorithm_name=="SPFA(LLL+SLF)") spfaPro();
    ShowMessgae("算法加载完毕，开始演示\n");
    timer->start(1000/speed);

}
std::vector<int> temp;
bool flag = false;
int index;
QList<Edge*> tempPath;
void showPlatform::showPath()
{
        if(path.isEmpty())
        {
            ShowMessgae("演示结束\n");
            timer->stop();
            timer->setInterval(1000/speed);
            return ;
        }
        else
        {
            nodes[curIndex=path.pop()]->setBrush(QColor(Qt::red));
            int nextIndex=curIndex;
            if(!path.isEmpty())
            {
                nextIndex=path.top();
            }

            for(int i=0;i<edges.size();i++)
            {
                if(edges[i]->s==curIndex && edges[i]->e==nextIndex)
                {
                    tempPath.append(edges[i]);//用于等下重置
                    QPen pen(QColor("#ff9f43"));
                    pen.setWidth(8);
                    pen.setStyle(Qt::DashLine);
                    pen.setJoinStyle(Qt::RoundJoin);//线条连接处圆角
                    pen.setCapStyle(Qt::RoundCap);//端点风格圆角
                    edges[i]->setPen(pen);
                }
            }
            std::vector<int> cur;
            std::stringstream text_stream(nodes[curIndex]->name->toPlainText().toStdString());
            std::string item;
            while (std::getline(text_stream, item, ' ')) {
                cur.push_back(stoi(item));
            }
            for(int i = 0;i < cur.size();i ++){
                flag = false;
                for(int j = 0;j < temp.size();j ++){
                    if(cur[i] == temp[j]) flag = true;
                }
                if(!flag){
                    index = i;
                }
            }
            temp = cur;
            qDebug() << cur[index];
            if(cur[index]==1){
                ShowMessgae("复杂度分析\n↓\n");
            }
            else if(cur[index]==2){
                ShowMessgae("基本算法思想\n↓\n");
            }
            else if(cur[index]==3){
                ShowMessgae("排序\n↓\n");
            }
            else if(cur[index]==4){
                ShowMessgae("线性表\n↓\n");
            }
            else if(cur[index]==5){
                ShowMessgae("散列表\n↓\n");
            }
            else if(cur[index]==6){
                ShowMessgae("树\n↓\n");
            }
            else if(cur[index]==7){
                ShowMessgae("图\n↓\n");
            }
            else if(cur[index]==8){
                ShowMessgae("搜索\n↓\n");
            }
            else if(cur[index]==9){
                ShowMessgae("查找\n↓\n");
            }
            else if(cur[index]==10){
                ShowMessgae("字符串匹配\n↓\n");
            }
            else if(cur[index]==11){
                ShowMessgae("其他\n↓\n");
            }
        }

}

void showPlatform::on_stop_but_clicked()
{
    timer->stop();
    ShowMessgae("暂停\n");
}

void showPlatform::on_big_but_clicked()
{
    ui->gView->scale(1.1,1.1);
}

void showPlatform::on_small_but_clicked()
{
    ui->gView->scale(0.9,0.9);
}

void showPlatform::on_horizontalSlider_sliderMoved(int value)
{
    qDebug()<<value;//0~99
    value=value==0?1:value;
    speed=value/10;//0.1~9.9,对应10s/step和0.1s/step
}


void showPlatform::on_comboBox_activated(const QString &arg1)
{
    algorithm_name=arg1;
    ShowMessgae("更换算法："+algorithm_name+"\n");

}

void showPlatform::on_reset_but_clicked()
{
    ShowMessgae("重置\n");
    for(int i=0;i<nodes.size();i++)
    {
        nodes[i]->setBrush(QBrush(QColor("#81ecec")));

    }
    for(int i=0;i<tempPath.size();i++)
    {
        QPen pen(QColor("#a29bfe"));
        pen.setWidth(8);
        pen.setStyle(Qt::DashLine);
        pen.setJoinStyle(Qt::RoundJoin);//线条连接处圆角
        pen.setCapStyle(Qt::RoundCap);//端点风格圆角
        tempPath[i]->setPen(pen);
    }
    tempPath.clear();
    curID=-1;
    start=-1;
    end=-1;
}


typedef std::pair<int,int> PII;
#define N 1000
#define INF 0x3f3f3f3f
int f[N][N];
bool vis[N];
int dis[N];
int pre[N];
int n;

void showPlatform::DJPro()
{
    path.clear();
    n=nodes.size();
    int m=edges.size();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            f[i][j]= i==j?0:INF;
        }
    }
    for(int i=0;i<m;i++)
    {
        f[edges[i]->s][edges[i]->e]=edges[i]->weight->toPlainText().toInt();
    }
    //算法选择在“开始”按钮点击之后才会选择然后执行算法
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    std::priority_queue<PII,std::vector<PII>,std::greater<PII>> heap;
    heap.push({0,start});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second,distance = t.first;
        dis[0] = 0;
        if(vis[ver]) continue;
        vis[ver] = true;
        for(int i = 0;i < n;i ++){
            if(dis[i] > distance + f[ver][i]){
                dis[i] = distance + f[ver][i];
                heap.push({dis[i],i});
                pre[i] = ver;
            }
        }
    }


    if(dis[end]==0x3f3f3f3f) ShowMessgae("不存在路径\n");
    else{
        int index=end;
        path.push(end);
        while(pre[index]!=start)
        {
            index=pre[index];
            path.push(index);
        }
        path.push(start);
    }
}
void showPlatform::DJ(){
    path.clear();
    n=nodes.size();
    int m=edges.size();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            f[i][j]= i==j?0:INF;
        }
    }
    for(int i=0;i<m;i++)
    {
        f[edges[i]->s][edges[i]->e]=edges[i]->weight->toPlainText().toInt();
    }
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[start] = 0;
    for(int i = 0;i < n;i ++){
        int t = -1;
        for(int j = 0;j < n;j ++)
            if(!vis[j]&&(t==-1||dis[j] < dis[t]))
                t = j;
        vis[t] = true;
        for(int j = 0;j < n;j ++){
            if(dis[j] > dis[t] + f[t][j]){
                dis[j] = dis[t] + f[t][j];
                pre[j] = t;
            }
        }
    }
    if(dis[end]>=0x3f3f3f3f/2) ShowMessgae("不存在路径\n");
    else{
        int index=end;
        path.push(end);
        while(pre[index]!=start)
        {
            index=pre[index];
            path.push(index);
        }
        path.push(start);
    }
}
int backup[N];
void showPlatform::bellman_ford(){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[start] = 0;
    n=nodes.size();
    int m=edges.size();
    for(int i = 0;i < n + 1 ; i++){
        memcpy(backup,dis,sizeof dis);
        for(int j = 0;j < m;j ++){
            auto e = edges[j];
            if(dis[e->e] > backup[e->s] + e->weight->toPlainText().toInt()){
                dis[e->e] = backup[e->s] + e->weight->toPlainText().toInt();
                pre[e->e] = e->s;
            }
        }
    }
    if(dis[end]>0x3f3f3f3f/2) ShowMessgae("不存在路径\n");
    else{
        int index=end;
        path.push(end);
        while(pre[index]!=start)
        {
            index=pre[index];
            path.push(index);
        }
        path.push(start);
    }
}
void showPlatform::spfa(){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[start] = 0;
    vis[start] = true;
    std::queue<int> q;
    q.push(start);
    n=nodes.size();
    int m=edges.size();
    while(!q.empty()){
        int a = q.front();
        q.pop();
        vis[a] = false;
        Edge* edge = nodes[a]->edge;//获得节点nodes[a]的一条出边
        while(edge){//遍历nodes[a]的所有出边
            int b = edge->e;//拿出出边的终点
            if(dis[b]>dis[a] + edge->weight->toPlainText().toInt()){//松弛判断
                dis[b] = dis[a] + edge->weight->toPlainText().toInt();
                if(!vis[b]) {
                    vis[b] = true;
                    q.push(b);
                }
                pre[b] = a;
            }
            edge = edge->next;//获得nodes[a]的下一条出边
        }
    }
    if(dis[end]>0x3f3f3f3f/2) ShowMessgae("不存在路径\n");
    else{
        int index=end;
        path.push(end);
        while(pre[index]!=start)
        {
            index=pre[index];
            path.push(index);
        }
        path.push(start);
    }
}

void showPlatform::spfaPro(){
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    std::deque<int> q;
    dis[start]=0;
    int a;
    q.push_back(start);
    int sum=dis[start];int num=1;
    vis[start]=true; //入队即true。
    while(!q.empty()){
        a=q.front();
        while(dis[a]*num>sum){
            //lll优化
            q.pop_front();
            q.push_back(a);
            a=q.front();
        }
        q.pop_front();
        sum-=dis[a];
        num--;
        vis[a]=false; //出队则false。
        Edge* edge = nodes[a]->edge;
        int v,w;
        //松弛操作
        while(edge){
            v = edge->e;
            w=edge->weight->toPlainText().toInt();
            if(dis[v]>dis[a]+w){
                dis[v]=dis[a]+w;//更新最短路径
                if(!vis[v]){
                    //判断是否在队列中
                    if(!q.empty()&&dis[v]>dis[q.front()]){
                        //和队头元素进行比较。
                        q.push_back(v);//大于入队尾
                    }
                    else q.push_front(v); //小于入队头
                    sum+=dis[v];
                    num++;
                    vis[v]=true;
                }
                pre[v] = a;
            }
            edge = edge->next;
        }
    }
    if(dis[end]>0x3f3f3f3f/2) ShowMessgae("不存在路径\n");
    else{
        int index=end;
        path.push(end);
        while(pre[index]!=start)
        {
            index=pre[index];
            path.push(index);
        }
        path.push(start);
    }
}
